package cn.genmer.test.security.algorithm.sort;

import cn.genmer.test.security.algorithm.entity.IntExtend;

/**
 * 冒泡排序
 *  3种优化思路： https://blog.csdn.net/Redmoon955331/article/details/53258186
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5,6,1,4,3,2,8,7};
        sortTEST(arr);
        printArray(arr);
    }

    /**
     * 冒泡
     * @param arr
     */
    public static void sort(int[] arr){
        int count = 0;
        for (int i=arr.length-1; i>0; i--){
            for (int j=0; j<i; j++){
                count++;
                if (arr[j] > arr[j+1]) {
                    swap(arr, j+1,j);
                }
            }
        }
        System.out.println(String.format("【初版】执行次数："+count));
    }
    /**
     * 冒泡 顺序循环的写法，第一次不知道为什么没通过
     * @param arr
     */
    public static void sort0(int[] arr){
        int size = arr.length;
        for (int i=0; i<size-1; i++){
            for (int j=0; j<size-1; j++){
                if (arr[j] > arr[j+1]) {
                    swap(arr, j+1,j);
                }
            }
        }
    }
    /**
     * 优化版本1 - 可以做到当某次循环后，数组已经有序，可以避免后续的无意义循环
     * @param arr
     */
    public static void sort1(int[] arr){
        if (arr.length <= 1) return;

        int count = 0;
        int changeFlag = 0;
        for (int i=arr.length-1; i>0; i--){
            changeFlag = 1;
            for (int j=0; j<i; j++){
                count++;
                if (arr[j] > arr[j+1]) {
                    swap(arr, j+1,j);
                    changeFlag = 0;
                }
            }
            // 如果第一轮之后，发现没有发生交换行为，即为有序
            if (changeFlag == 1) break;
        }
        System.out.println(String.format("【优化1】执行次数："+count));
    }

    /**
     * 优化版本2 - 通过第一次的全部全部对比，得出结论：最后一次发生交换的位置之后的数据都是有序的，
     * 我们可以直接忽略这部分数据
     * @param arr
     */
    public static void sort2(int[] arr) {
        int size = arr.length;
        if (size <= 1) return;

        int changeFlag = 0;
        int maxIndex = size-1;
        int innerIndex = size-1;
        int count = 0;
        for (int i=0; i<size-1; i++){
            changeFlag = 1;
            for (int j=0; j<innerIndex; j++){
                count++;
                if (arr[j] > arr[j+1]) {
                    swap(arr, j+1,j);
                    changeFlag = 0;
                    maxIndex = j;
                }
            }
            // 如果第一轮之后，发现没有发生交换行为，即为有序
            if (changeFlag == 1) break;

            innerIndex = maxIndex;
        }
        System.out.println(String.format("【优化2】执行次数："+count));
    }

    /**
     * 优化版本3 - 正反交替扫描， 正着扫描得到最大值， 反着扫描得到最小值（或者颠倒顺序），
     * 这样我们每次得到无序区的最大值和最小值只对它们排序就可以了。
     * @param arr
     */
    public static void sort3(int[] arr) {
        int size = arr.length;
        if (size <= 1) return;

        int changeFlag = 0;
        int maxIndex = size-1;
        int minIndex = 0;
        int index = size-1;
        int count = 0;
        for (int i=0; i<size-1; i++){
            changeFlag = 1;
            for (int j=0; j<index; j++){
                count++;
                if (arr[j] > arr[j+1]) {
                    swap(arr, j+1,j);
                    changeFlag = 0;
                    maxIndex = j;
                }
            }
            // 如果第一轮之后，发现没有发生交换行为，即为有序
            if (changeFlag == 1) break;

            index = maxIndex;

            changeFlag = 1;
            for (int j=size-1; j>minIndex; j--){
                count++;
                if (arr[j] < arr[j-1]) {
                    swap(arr, j-1,j);
                    changeFlag = 0;
                }
            }
            // 如果第一轮之后，发现没有发生交换行为，即为有序
            if (changeFlag == 1) break;

            minIndex++;
        }
        System.out.println(String.format("【优化3】执行次数："+count));

    }

    /**
     * 测试记忆版本
     * 【2022.11.20】【初始】不通过 i j的循环边界不清楚
     *               【优化1】通过
     *               【优化2】不通过，innerCycleNum那里我一开始直接改size，无效
     * 【2022.11.30】【初始】 通过，两层循环，直接交换
     *               【优化1】通过， 判断某次循环是否没交换，判定位已经有序，退出
     *               【优化2】通过【一次交换过后，最大值后的都是有序的】，节省循环次数
     * @param arr
     */
    public static void sortTEST(int[] arr){
        int len = arr.length-1;
        int changeFlag = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len +1; j++) {
                if (arr[i] > arr[j]) {
                    swap(arr,i,j);
                    changeFlag =1;
                }
            }
            if (changeFlag == 0) return;
        }
    }

    /**
     * 验证算法稳定性版本
     * @param arr
     */
    public static void sort2(IntExtend[] arr){
        for (int i=arr.length-1; i>0; i--){
            for (int j=0; j<i; j++){
                if (arr[j].getValue() > arr[j+1].getValue()) {
                    swapExtent(arr, j+1,j);
                }
            }
        }
    }
    private static void swap(int[] arr, int pos1, int pos2){
        int temp = arr[pos1];
        arr[pos1] = arr[pos2];
        arr[pos2] = temp;
    }
    private static void swapExtent(IntExtend[] arr, int pos1, int pos2){
        IntExtend temp = arr[pos1];
        arr[pos1] = arr[pos2];
        arr[pos2] = temp;
    }
    public static void printArray(int [] arr){
        for (int i: arr){
            System.out.print(i + " ");
        }
    }
    public static void printArray(IntExtend [] arr){
        for (IntExtend i: arr){
            System.out.print(i.getIndex() + " ");
        }
    }
}
